package primalgorithms.array;

import java.util.Arrays;
import java.util.HashMap;

public class _09TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        /**
         *时间复杂度O(n2)
         *双指针法
        int len = nums.length;
        if(len < 2){
            return null;
        }
        int left = 0;
        int[] res = new int[2];
        for (;left < len-1;left++){
            for (int right = left+1;right < len;right++){
                if(nums[left] + nums[right] == target){
                    res[0] = left;
                    res[1] = right;
                    return res;
                }
            }
        }
        //执行到此处，说明没有满足题意的两个数组下标
        return null;
        */
        //下面采用另一种双指针法
        int len = nums.length;
        if(len < 2){
            return null;
        }
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        //向哈希表中添加元素
        //key为数组元素，value为数组下标
        for (int i = 0;i < len;i++){
            if(hashMap.containsKey(target - nums[i])){
                //返回一个数组的简便方法
                return new int[] {hashMap.get(target - nums[i]),i};
            }
            //表中没有与num[i]相加和为target的元素
            //此时需要在哈希表中添加该元素
            hashMap.put(nums[i],i);
        }
        return null;
    }
}
